ICPC Live Archive/3928 - Ballroom lights/help/gomox.ar-pap-2010-d9b17e5cb110/tpa/bishops/main.cpp

   1 #include <iostream>
   2 #include <vector>
   3
   4 using namespace std;
   5
   6 typedef unsigned int uint;
   7 typedef unsigned long long int uint64;
   8
   9 #define forsn(i, s, n)          for (uint i = (s); i < (n); i++)
  10 #define forn(i, n)              forsn (i, 0, n)
  11
  12 #define num_diagonals(n)        (2 * (n) - 1)
  13
  14 typedef vector<uint64> vuint64;
  15 typedef vector<vuint64> vvuint64;
  16
  17 #define BLACK 0
  18 #define WHITE 1
  19 // m: output matrix, should have 2 rows and k + 1 columns
  20 // black_white == 1 iff we are dealing with the white cells and an odd value of n
  21 vuint64 *put_bishops_monochrome(uint n, uint k, bool black_white, vvuint64& m) {
  22         bool row = 0;
  23
  24         m[0][0] = 1; // we can always put 0 bishops
  25         m[1][0] = 1;
  26
  27         forn (i, n - black_white) {
  28                 uint num_cells = 2 * (i / 2) + 1 + black_white;
  29                 forsn (j, 1, k + 1) {
  30                         m[row][j] = m[!row][j] + m[!row][j - 1] * (num_cells - (j - 1));
  31                 }
  32                 row = !row;
  33         }
  34         return &m[!row];
  35 }
  36
  37 uint64 put_bishops(uint n, uint k) {
  38         if (k == 0) return 1;
  39         if (k == 1 && n == 1) return 1;
  40         if (k > num_diagonals(n) - 1) return 0;
  41
  42         vvuint64 matrix_black(2, vuint64(k + 1, 0));
  43         vvuint64 matrix_white(2, vuint64(k + 1, 0));
  44
  45         vuint64& black(*put_bishops_monochrome(n, k, BLACK, matrix_black));
  46         vuint64& white(n % 2 == 0 ? black : *put_bishops_monochrome(n, k, WHITE, matrix_white));
  47
  48         uint64 ways = 0;
  49         uint lower = k > (n - 1) ? k - (n - 1) : 0;
  50         uint upper = min(k, n - 1) + 1;
  51         forsn (a, lower, upper) {
  52                 ways += black[a] * white[k - a];
  53         }
  54         return ways;
  55 }
  56
  57 int main() {
  58         uint n, k;
  59         while (true) {
  60                 scanf("%u %u", &n, &k);
  61                 if (n == 0 && k == 0) break;
  62                 cout << put_bishops(n, k) << endl;
  63         }
  64         return 0;
  65 }
  66